Hereinafter, a “Q” prefix in a word of phrase is indicative of a reference of that word or phrase in a quantum computing context unless expressly distinguished where used.
Molecules and subatomic particles follow the laws of quantum mechanics, a branch of physics that explores how the physical world works at the most fundamental levels. At this level, particles behave in strange ways, taking on more than one state at the same time, and interacting with other particles that are very far away. Quantum computing harnesses these quantum phenomena to process information.
The computers we use today are known as classical computers (also referred to herein as “conventional” computers or conventional nodes, or “CN”). A conventional computer uses a conventional processor fabricated using semiconductor materials and technology, a semiconductor memory, and a magnetic or solid-state storage device, in what is known as a Von Neumann architecture. Particularly, the processors in conventional computers are binary processors, i.e., operating on binary data represented in 1 and 0.
A quantum processor (q-processor) uses the odd nature of entangled qubit devices (compactly referred to herein as “qubit,” plural “qubits”) to perform computational tasks. In the particular realms where quantum mechanics operates, particles of matter can exist in multiple states-such as an “on” state, an “off” state, and both “on” and “off” states simultaneously. Where binary computing using semiconductor processors is limited to using just the on and off states (equivalent to 1 and 0 in binary code), a quantum processor harnesses these quantum states of matter to output signals that are usable in data computing.
Conventional computers encode information in bits. Each bit can take the value of 1 or 0. These 1s and 0s act as on/off switches that ultimately drive computer functions. Quantum computers, on the other hand, are based on qubits, which operate according to two key principles of quantum physics: superposition and entanglement. Superposition means that each qubit can represent both a 1 and a 0 at the same time. Entanglement means that qubits in a superposition can be correlated with each other in a non-classical way; that is, the state of one (whether it is a 1 or a 0 or both) can depend on the state of another, and that there is more information that can be ascertained about the two qubits when they are entangled than when they are treated individually.
Using these two principles, qubits operate as more sophisticated processors of information, enabling quantum computers to function in ways that allow them to solve difficult problems that are intractable using conventional computers. IBM has successfully constructed and demonstrated the operability of a quantum processor using superconducting qubits (IBM is a registered trademark of International Business Machines corporation in the United States and in other countries.)
The illustrative embodiments recognize that quantum processors can perform variational algorithms which presently available conventional processors are either incapable of performing or can only perform with undesirable accuracy or computational resource consumption. Variational algorithms use a trial wavefunction which is varied to determine an upper bound to a ground state energy of a quantum system. A wavefunction is a mathematical description, such as, of a quantum state of a quantum system. A quantum state is represented on a quantum processor as a series of quantum logic gates acting on qubits. Each quantum state of a quantum system includes a corresponding energy value.
The total energy of the ground state of the quantum system corresponds to a minimum possible value of the total energy of the quantum system. A Hamiltonian is an operator that describes the total energy of a quantum state. A Hamiltonian operator acting on a wavefunction determines a value corresponding to the total energy of the quantum state.
In order to compute an upper bound to the ground state energy of a quantum system, variational algorithms perform numerous evaluations beginning with an initial wavefunction. Each evaluation computes a total energy of a quantum state corresponding to the wavefunction being evaluated. Variational algorithms can then alter parameters of the evaluated wavefunction to generate a new wavefunction, such as, altering at least one quantum logic gate of a set of quantum logic gates to perform a rotation on a qubit. Evaluation of the new wavefunction computes a total energy of the new quantum state corresponding to the new wavefunction. The variational algorithm compares the total energy of the previous wavefunction to the total energy of the new wavefunction.
A conventional processor executes an optimization algorithm that varies the parameters of the wavefunction. A quantum processor computes the corresponding total energy of the wavefunction. Based on the comparison between the total energy of the new wavefunction and the previous wavefunction, the optimization algorithm determines how to vary the parameters of the wavefunction in order to minimize the computed total energy of the quantum system.
A variational algorithm can continue performing evaluations until the computed total energy is relatively stable, such as, successive evaluations computing a total energy within a threshold percentage. The stable computed total energy from the final evaluation corresponds to an upper bound of the minimum energy of the ground state of the quantum system. The corresponding wavefunction represents an approximation of the eigenfunction of the quantum system.
The illustrative embodiments recognize that any general combinatorial optimization problem can be solved using variational algorithms. Combinatorial optimization involves determining a minima or maxima of an objective function. For example, the travelling salesman problem involves determining the shortest possible path between n cities that visits each city exactly once. Combinatorial optimization involves determining the solution (paths between the cities) with the least cost. The solution space of a combinatorial optimization problem is the set of possible solutions. A conditional value at risk focuses on a specific subset of the set of solutions. For example, financial risk measurement cases may look at the expected return (gain/loss) in the worst five percent of cases.
The illustrative embodiments recognize that quantum states of particles in a quantum system can be entangled. Entangled quantum states cannot be described independently of the state of other particles in the quantum system. Entangled quantum states require a description of the quantum system as a whole. The illustrative embodiments recognize that each iteration of a variational algorithm determines only a single potential solution for the quantum state of the quantum system.
The illustrative embodiments recognize that the solution space of combinatorial optimization problems is typically too large to exhaustively search using conventional computers. For many combinatorial optimization problems, computing a sufficiently large sample of the entire solution space is cost prohibitive or not currently possible using conventional computing but may be possible using quantum computing architectures.
The illustrative embodiments further recognize that conventional variational algorithms for approximating the true solution of a combinatorial optimization problem focus on an average over the entire set of solutions (solution space) for each iteration of the variational algorithm. The illustrative embodiments recognize that some potential solutions in the subset of the set of solutions can be closer to the true solution of the combinatorial optimization problem. The illustrative embodiments also recognize that taking an average of the potential solutions closest to a minima or maxima solution may help the variational algorithm to determine a closer approximation to the true solution.
Furthermore, because quantum computing resources are scarce and expensive, a need exists to compute the sufficiently large solution space sample, and their maxima and minima, at the least possible quantum computing cost. Therefore, the illustrative embodiments recognize that a need exists for a novel method to execute a variational algorithm on quantum computing platforms in such a way that the quantum computing cost for producing large solution space samples and their maxima and minima are minimized without a loss of accuracy.